There are n cities numbered from 1 to n.
You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)
Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.
Example 1:
Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] Output: 6 Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.
Example 2:
Input: n = 4, connections = [[1,2,3],[3,4,4]] Output: -1 Explanation: There is no way to connect all cities even if all edges are used.
Note:
1 <= n <= 100001 <= connections.length <= 100001 <= connections[i][0], connections[i][1] <= n0 <= connections[i][2] <= 105connections[i][0] != connections[i][1]
Average Rating: 4.46 (13 votes)
Solution
Approach 1: Minimum Spanning Tree (Using Kruskal's algorithm)
Intuition
If we model the cities and connections as a graph, each connection is an edge (undirected) and each city is a node of the graph. We need to find a subset of edges which connects all the nodes of the graph with the minimum possible total weight. This is by definition the Minimum Spanning Tree or MST of a graph.
Algorithm
There are a variety of algorithms that we can use to obtain the MST of a graph. We will use Kruskal's algorithm here, which is implemented using the Disjoint set Union-Find data structure.
In order to obtain the MST using Kruskal's algorithm, we first sort all the connections (edges) present in the graph based on their weights (in increasing order) and will iterate over them one by one. The objective here is to greedily pick edges that will help us to connect more nodes in the graph. Each time we find a new edge which does not result in a cycle with the edges selected so far, we add that edge in the final MST. We keep doing this till we have obtained the MST which connects all the nodes in the graph (i.e. connects all the cities using the connections).
Disjoint-set union find can be implemented in a couple of ways. A plain union find is shown below which keeps the track of the parent of each node (initially parent of i is set to itself, i.e. i) and performs the union and find using a helper method getRoot.
The above implementation can be made faster by incorporating Path compression. Here, while obtaining the root, we compress the path by assigning the grandparent of the node as the parent (thereby skipping connections and moving nodes closer to the root). We modify the Find method to implement path compression.
This can be made even faster using a technique known as Weighted Union. In this technique, in addition to the parent nodes, we also keep the weights of each of the nodes. Every time we take union, the root node with more weight (i.e. having more elements in the corresponding set) is used as the parent node of the other node. We initialize the weight corresponding to each node as 1 initially, as each element belongs to it's own set in the beginning. Below is the implementation of this idea (we modify Union method).
If we combine both Path compression and Weighted Union, it takes log∗N for the union and find operations in case of Disjoint-set union link. Here log∗N is an extremely slow-growing inverse Ackermann function a.k.a Iterated logarithm and practically does not exceed 5. Hence it can be treated as a constant for implementation purposes.
We can combine all the concepts we have seen above in order to implement Kruskal's algorithm for obtaining MST of a graph. Below is the implementation of this.
Complexity Analysis
-
Time complexity: Assuming N to be the total number of nodes (cities) and M to be the total number of edges (connections). Sorting all the M connections will take O(M⋅logM). Performing union find each time will take log∗N (Iterated logarithm). Hence for M edges, it's O(M⋅log∗N) which is practically O(M) as the value of iterated logarithm, log∗N never exceeds 5.
-
Space complexity: O(N), space required by
parentsandweights.
Last Edit: January 13, 2021 2:40 AM
While it's a nice problem to learn new algorithm at the same time this is absolutely disgusting job interview question. Not even mentioning the fact that Kruskal didn't come up with this idea in 45 minutes, the most important thing is that there is a very low space for candidate to show his ability to solve problems. The best INTERVIEW questions (maybe even hard, final complexity doesn't matter) can be solved using easy "brute force" ideas but they should allow candidates to iteratively improve the initial solution to come up with the most optimal (most optimal that candidate came up with in 45 mins). And this path from the simple naive idea to something more optimal (plus candidate's ability to communicate and think about complexity of his solution) is the most crucial thing for interviewer to evaluate candidate and give a hire/no hire recommendation.
So, what I want to say: fck this kind of INTERVIEW questions. But I love that this problem helps me to learn smth new (or forgotten old :).
January 5, 2021 7:21 AM
Well... I don't think I can pass a minimum spanning tree question like this.
June 3, 2021 5:39 AM
The weight in DisjointSet is useless!?
February 4, 2021 3:28 AM
Much cleaner solution Python3: Straightforward Kruskal and UnionFind algorithm
Runtime: 804 ms, faster than 17.54% of Python3 online submissions for Connecting Cities With Minimum Cost.
Memory Usage: 20.3 MB, less than 31.98% of Python3 online submissions for Connecting Cities With Minimum Cost.
class UnionFind:
def __init__(self, N):
self.ufid = [i for i in range (N + 1)]
def find(self, node):
root = node
while root != self.ufid[root]:
root = self.ufid[root]
# path compresssion
p = node
while p != root:
parent = self.ufid[p]
self.ufid[p] = root
p = parent
return root
def union(self, x, y):
root1, root2 = self.find(x), self.find(y)
if root1 == root2:
return False
self.ufid[root1] = root2
return True
class Solution:
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
connections.sort(key = lambda x : x[2])
uf = UnionFind(N)
cost = 0
vertices = set()
for fro, to, w in connections:
vertices.add(fro)
vertices.add(to)
if uf.union(fro, to):
cost += w
# checking if all the vertices are accounted for
if len(vertices) != N:
return -1
conn = set()
# making sure there is only one connected component
for i in range(1, N):
conn.add(uf.find(i))
return cost if len(conn) == 1 else -1
Last Edit: April 11, 2021 7:32 AM
Python code, using min heap instead of sorting (this will give us a better time complexity in cases where there are many duplicate connections with higher costs that we never end up using):
import heapq
class Solution:
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
def find(i):
if parent[i] != i: parent[i] = find(parent[i])
return parent[i]
parent, rank = list(range(N+1)), [0]*(N+1)
connections = [[cost, u, v] for u, v, cost in connections]
heapq.heapify(connections)
res = cnt = 0
while connections and cnt < N-1:
cost, u, v = heapq.heappop(connections)
u_par, v_par = find(u), find(v)
if u_par != v_par:
cnt += 1
res += cost
if rank[u_par] < rank[v_par]: parent[u_par] = v_par
else:
parent[v_par] = u_par
if rank[u_par] == rank[v_par]: rank[u_par] += 1
return res if cnt == N-1 else -1
March 31, 2021 2:41 AM
The time complexity seems wrong. It should be O(MlogM + M) not O(M)
January 9, 2021 3:22 PM
kruskal algorithm is much easier
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int minimumCost(int n, vector<vector<int>>& connections) { }};